home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Language/OS - Multiplatform Resource Library
/
LANGUAGE OS.iso
/
pcr
/
pcr4_4.lha
/
DIST
/
threads
/
ThreadsQueues.c
< prev
next >
Wrap
C/C++ Source or Header
|
1992-02-18
|
13KB
|
598 lines
/* begincopyright
Copyright (c) 1988 Xerox Corporation. All rights reserved.
Use and copying of this software and preparation of derivative works based
upon this software are permitted. Any distribution of this software or
derivative works must comply with all applicable United States export
control laws. This software is made available AS IS, and Xerox Corporation
makes no warranty about the software, its performance or its conformity to
any specification. Any person obtaining a copy of this software is requested
to send their name and post office or electronic mail address to:
PCR Coordinator
Xerox PARC
3333 Coyote Hill Rd.
Palo Alto, CA
endcopyright */
/*
* ThreadsQueues.c
*
* Demers, January 25, 1991 4:25:23 pm PST
* Theimer, January 25, 1991 4:25:26 pm PST
*/
#include "xr/BasicTypes.h"
#include "xr/Threads.h"
#include "xr/ThreadsBackdoor.h"
#include "xr/ThreadsPrivate.h"
#include "xr/ThreadsMsgPrivate.h"
#include <sys/time.h>
/* debugging only */
#define SS1_HAT_KLUDGE 1
long XR_GetMicroseconds()
{
struct timeval t;
XR_GetTimeOfDay(&t, 0);
return(((t.tv_sec & 0x3ff) * 1000000) + t.tv_usec);
}
/*
* Thread Queues
*/
void
XR_AddHdTQ (tq, t)
XR_TQ tq;
XR_Thread t;
{
XR_ASSERT( t->t_next == NIL, "AddHdTQ a" );
t->t_tq = tq;
if( tq->tq_tail == NIL ) {
tq->tq_tail = t->t_next = t;
} else {
XR_Thread tl = tq->tq_tail;
t->t_next = tl->t_next;
tl->t_next = t;
}
}
void
XR_AddTlTQ (tq, t)
XR_TQ tq;
XR_Thread t;
{
XR_ASSERT( t->t_next == NIL, "AddTlTQ b" );
t->t_tq = tq;
if( tq->tq_tail == NIL ) {
tq->tq_tail = t->t_next = t;
} else {
XR_Thread tl = tq->tq_tail;
t->t_next = tl->t_next;
tq->tq_tail = tl->t_next = t;
}
}
XR_Thread
XR_RemHdTQ (tq)
XR_TQ tq;
{
XR_Thread hd;
XR_ASSERT( tq->tq_tail != NIL, "RemHdPQ a" );
if( (hd = tq->tq_tail->t_next) == tq->tq_tail ) {
tq->tq_tail = NIL;
} else {
tq->tq_tail->t_next = hd->t_next;
}
hd->t_next = NIL;
hd->t_tq = NIL;
return( hd );
}
void
XR_RemTQ (t)
XR_Thread t;
{
XR_TQ tq;
XR_Thread each;
if( (tq = t->t_tq) == NIL ) return;
if( (each = tq->tq_tail) == NIL ) {
XR_Panic("RemTQ 0");
}
for(;;) {
XR_Thread next = each->t_next;
if( next == t ) break;
if( next == tq->tq_tail ) return;
each = next;
}
if( each == t ) /* singleton */ {
tq->tq_tail = NIL;
} else if( t == tq->tq_tail ) /* removing tail */ {
each->t_next = tq->tq_tail = t->t_next;
} else /* removing from elsewhere */ {
each->t_next = t->t_next;
}
t->t_next = NIL;
t->t_tq = NIL;
}
/*
* Wait Queues
*/
void
XR_AddHdWQ (wq, t)
XR_WQ wq;
XR_Thread t;
{
XR_ASSERT( t->t_wNext == NIL, "AddHdWQ a" );
t->t_wq = wq;
if( wq->wq_tail == NIL ) {
wq->wq_tail = t->t_wNext = t;
} else {
register XR_Thread tl = wq->wq_tail;
t->t_wNext = tl->t_wNext;
tl->t_wNext = t;
}
}
void
XR_AddTlWQ (wq, t)
XR_WQ wq;
XR_Thread t;
{
XR_ASSERT( t->t_wNext == NIL, "AddTlWQ a" );
t->t_wq = wq;
if( wq->wq_tail == NIL ) {
wq->wq_tail = t->t_wNext = t;
} else {
XR_Thread tl = wq->wq_tail;
t->t_wNext = tl->t_wNext;
wq->wq_tail = tl->t_wNext = t;
}
}
XR_Thread
XR_RemHdWQ (wq)
XR_WQ wq;
{
XR_Thread hd;
XR_ASSERT( wq->wq_tail != NIL, "RemHdWQ a" );
if( (hd = wq->wq_tail->t_wNext) == wq->wq_tail ) {
wq->wq_tail = NIL;
} else {
wq->wq_tail->t_wNext = hd->t_wNext;
}
hd->t_wNext = NIL;
hd->t_wq = NIL;
return( hd );
}
void
XR_RemWQ (t)
XR_Thread t;
{
XR_Thread each;
XR_WQ wq = t->t_wq;
if( wq == NIL ) return;
if( (each = wq->wq_tail) == NIL )
XR_Panic("RemWQ 0");
for(;;) {
XR_Thread next = each->t_wNext;
if( next == t ) break;
if( next == wq->wq_tail )
XR_Panic("RemWQ 1");
each = next;
}
if( each == t ) /* singleton */ {
wq->wq_tail = NIL;
} else if( t == wq->wq_tail ) /* removing tail */ {
each->t_wNext = wq->wq_tail = t->t_wNext;
} else /* removing from elsewhere */ {
each->t_wNext = t->t_wNext;
}
t->t_wNext = NIL;
t->t_wq = NIL;
}
#if (SS1_HAT_KLUDGE)
/*
* RequestResched hacks for HAT stuff on SPARCStation-1
*/
unsigned XR_hatCtl = 0;
# define XR_HATCTL_NOT_OTHER 1
# define XR_HATCTL_NOT_ALL 2
# define XR_HATCTL_NOT_SELF 4
# define XR_HATCTL_NOT_NAKED 8
unsigned
XR_GetHATCtl()
{
return XR_hatCtl;
}
unsigned
XR_SetHATCtl(new)
unsigned new;
{
unsigned old = XR_hatCtl;
XR_hatCtl = new;
return old;
}
static void
XR_ComplexRequestResched(vpe)
XR_VPE vpe;
{
unsigned skipBits;
if( (skipBits = XR_hatCtl) != 0 ) {
if( XR_vpe == NIL ) {
if( skipBits & XR_HATCTL_NOT_NAKED ) return;
} else if( vpe == NIL ) {
if( skipBits & XR_HATCTL_NOT_ALL ) return;
if( skipBits & XR_HATCTL_NOT_OTHER ) vpe = XR_vpe;
} else if( vpe == XR_vpe ) {
if( skipBits & XR_HATCTL_NOT_SELF ) return;
} else {
if( skipBits & XR_HATCTL_NOT_OTHER ) return;
}
}
XR_RequestResched(vpe);
}
#define XR_RequestResched XR_ComplexRequestResched
#endif /* SS1_HAT_KLUDGE */
/*
* Monitor Locks
*/
void
XR_InitializeMonitor (ml)
XR_ML ml;
{
XR_InitWQ(&(ml->ml_wq));
ml->ml_holder = NIL;
}
void
XR_MonitorEntryOutOfLine (ml)
XR_ML ml;
{
for(;;) {
XR_AcquireGSL(&(ml->ml_gsl));
if( ml->ml_holder == NIL ) break;
XR_AddTlWQ(&(ml->ml_wq), XR_currThread);
XR_Switch( ml->ml_holder, XR_SSTAT_WAIT_ML, XR_SWSTAT_THREAD );
}
ml->ml_holder = XR_currThread;
XR_ReleaseGSL(&(ml->ml_gsl));
}
#if (!XR_MONITOR_ENTRY)
void
XR_MonitorEntry (ml)
XR_ML ml;
{
if( XR_TryGSL(&(ml->ml_gsl)) ) {
if( ml->ml_holder == NIL ) {
ml->ml_holder = XR_currThread;
XR_ReleaseGSL(&(ml->ml_gsl));
return;
}
XR_ReleaseGSL(&(ml->ml_gsl));
}
XR_MonitorEntryOutOfLine (ml);
}
#endif
void
XR_MonitorExitOutOfLine (ml)
XR_ML ml;
{
XR_VPE chosenVPE = NIL;
XR_Thread chosenThread = NIL;
XR_VPE vpeToReschedOnMonitorExit;
vpeToReschedOnMonitorExit =
(XR_VPE)(XR_currThread->t_vpeToReschedOnMonitorExit);
XR_currThread->t_vpeToReschedOnMonitorExit = NIL;
XR_AcquireGSL(&(ml->ml_gsl));
if( XR_NonemptyWQ(&(ml->ml_wq)) )
chosenThread = XR_RemHdWQ(&(ml->ml_wq));
ml->ml_holder = NIL;
XR_ReleaseGSL(&(ml->ml_gsl));
if (chosenThread != NIL) {
chosenVPE = XR_SetThreadReady(chosenThread);
}
if( chosenVPE == NIL ) {
chosenVPE = vpeToReschedOnMonitorExit;
} else /* chosenVPE != NIL */ {
if( (vpeToReschedOnMonitorExit != NIL)
&& (vpeToReschedOnMonitorExit != chosenVPE) )
chosenVPE = DEFERRED_RESCHED_ALL;
}
if( chosenVPE != NIL ) {
if( chosenVPE == XR_vpe ) {
XR_Switch(NIL, XR_SSTAT_READY, XR_SWSTAT_THREAD);
} else {
XR_RequestResched(
(chosenVPE == DEFERRED_RESCHED_ALL) ? NIL : chosenVPE
);
/* We held the metalock for a little while */
XR_CheckReschedRequest();
}
} else {
XR_CheckReschedRequest();
}
}
#if (!XR_MONITOR_EXIT)
void
XR_MonitorExit (ml)
XR_ML ml;
{
XR_VPE vpeToReschedOnMonitorExit
= (XR_VPE)(XR_currThread->t_vpeToReschedOnMonitorExit);
if( XR_TryGSL(&(ml->ml_gsl)) ) {
if( (! XR_NonemptyWQ(&(ml->ml_wq)))
&& (vpeToReschedOnMonitorExit == NIL) ) {
ml->ml_holder = NIL;
XR_ReleaseGSL(&(ml->ml_gsl));
return;
}
XR_ReleaseGSL(&(ml->ml_gsl));
}
XR_MonitorExitOutOfLine (ml);
}
#endif
/*
* Condition Variables
*/
void
XR_InitializeCondition (cv, timeout)
XR_CV cv;
XR_Ticks timeout;
{
XR_InitWQ(&(cv->cv_wq));
cv->cv_timeout = timeout;
cv->cv_abortable = FALSE;
cv->cv_wakeupWaiting = FALSE;
}
int
XR_WaitCV (cv, ml)
XR_CV cv;
XR_ML ml;
{
XR_currThread->t_abortable = cv->cv_abortable;
XR_AcquireGSL(&(cv->cv_gsl));
if( cv->cv_wakeupWaiting ) {
cv->cv_wakeupWaiting = FALSE;
XR_ReleaseGSL(&(cv->cv_gsl));
} else {
if( ml != NIL ) {
XR_MonitorExit (ml);
XR_currThread->t_mlNeeded = ml;
}
XR_AddTlWQ(&(cv->cv_wq), XR_currThread);
XR_Switch(NIL, XR_SSTAT_WAIT_CV, XR_SWSTAT_THREAD);
if( ml != NIL ) {
XR_MonitorEntry (ml);
XR_currThread->t_mlNeeded = NIL;
}
}
if( XR_currThread->t_abortRequest && XR_currThread->t_abortable ) {
XR_currThread->t_abortRequest = FALSE;
return(-1);
}
return(0);
}
/*
* Notify, Broadcast and NakedNotify must be careful to avoid smashes
* in the case where the condition is allocated on the
* notify-ee's local frame.
*
* ajd+chh July 16, 1990 2:29:12 pm PDT
*/
void
XR_Notify (cv)
XR_CV cv;
{
XR_VPE chosenVPE;
XR_Thread chosenThread;
XR_ML mlNeeded;
XR_AcquireGSL(&(cv->cv_gsl));
if( XR_NonemptyWQ(&(cv->cv_wq)) ) {
chosenThread = XR_RemHdWQ(&(cv->cv_wq));
} else {
chosenThread = NIL;
}
XR_ReleaseGSL(&(cv->cv_gsl));
if( chosenThread != NIL ) {
/* defer resched if we're holding lock needed by chosenThread mmt+ajd */
chosenVPE = XR_SetThreadReady( chosenThread );
if( ((mlNeeded = chosenThread->t_mlNeeded) != NIL)
&& (mlNeeded->ml_holder == XR_currThread) ) {
XR_currThread->t_vpeToReschedOnMonitorExit = chosenVPE;
XR_CheckReschedRequest();
} else {
if( chosenVPE == XR_vpe ) {
XR_Switch(NIL, XR_SSTAT_READY, XR_SWSTAT_THREAD);
} else if( chosenVPE != NIL ) {
XR_RequestResched(chosenVPE);
XR_CheckReschedRequest();
}
}
}
}
#define XR_BCAST_LIST_ENTRIES 15
typedef struct XR_BcastTListRep {
struct XR_BcastTListRep *bctl_prev;
XR_Thread bctl_t[XR_BCAST_LIST_ENTRIES];
} * XR_BcastTList;
static void
XR_BroadcastInner (cv, otherNotifyees)
XR_CV cv;
XR_BcastTList otherNotifyees;
{
int i = 0;
struct XR_BcastTListRep bctl;
XR_BcastTList bctlp;
XR_VPE chosenVPE = NIL;
int numChosen = 0;
XR_VPE tvpe;
bool canDefer;
if( otherNotifyees == NIL ) XR_AcquireGSL(&(cv->cv_gsl));
bctl.bctl_prev = otherNotifyees;
while( XR_NonemptyWQ(&(cv->cv_wq)) ) {
if( i >= XR_BCAST_LIST_ENTRIES ) {
XR_BroadcastInner(cv, &bctl);
return;
}
bctl.bctl_t[i] = XR_RemHdWQ(&(cv->cv_wq));
i++;
}
XR_ReleaseGSL(&(cv->cv_gsl));
canDefer = TRUE;
bctlp = &bctl;
while( bctlp != NIL ) {
if( i == 0 ) {
bctlp = bctlp->bctl_prev;
i = XR_BCAST_LIST_ENTRIES;
} else {
XR_Thread chosenThread;
XR_ML mlNeeded;
i--;
chosenThread = bctlp->bctl_t[i];
tvpe = XR_SetThreadReady( chosenThread );
if( tvpe != NIL ) {
/* see if this thread inhibits resched deferral mmt+ajd */
if( ((mlNeeded = chosenThread->t_mlNeeded) == NIL)
|| (mlNeeded->ml_holder != XR_currThread) ) {
canDefer = FALSE;
}
numChosen++; chosenVPE = tvpe;
}
}
}
if( numChosen == 0 ) {
return;
} else if( numChosen > 1 ) {
if( canDefer )
XR_currThread->t_vpeToReschedOnMonitorExit = DEFERRED_RESCHED_ALL;
else
XR_RequestResched(NIL);
} else /* numChosen == 1 */ {
if( canDefer ) {
XR_currThread->t_vpeToReschedOnMonitorExit = chosenVPE;
} else /* (!canDefer) */ {
if( chosenVPE == XR_vpe ) {
XR_Switch(NIL, XR_SSTAT_READY, XR_SWSTAT_THREAD);
} else if( chosenVPE != NIL ) {
XR_RequestResched(chosenVPE);
}
}
}
/* XR_SetThreadReady held the metalock */
XR_CheckReschedRequest();
}
void
XR_Broadcast (cv)
XR_CV cv;
{
XR_BroadcastInner(cv, NIL);
}
XR_VPE
XR_NakedNotifyInner (icv)
XR_CV icv;
{
XR_Thread chosenThread;
XR_VPE chosenVPE = NIL;
/* acquire gsl protecting monitor using psl op! */
XR_AcquirePSL(((XR_PSL)(&(icv->cv_gsl))));
if( XR_NonemptyWQ(&(icv->cv_wq)) ) {
chosenThread = XR_RemHdWQ(&(icv->cv_wq));
} else {
icv->cv_wakeupWaiting = TRUE;
chosenThread = NIL;
}
/* release gsl protecting monitor using psl op! */
XR_ReleasePSL(((XR_PSL)(&(icv->cv_gsl))));
if( chosenThread != NIL ) {
chosenVPE = XR_SetThreadReady( chosenThread );
if(XR_vpe != NIL) XR_CheckReschedRequest();
}
return chosenVPE;
}
void
XR_NakedNotify (icv)
XR_CV icv;
{
XR_VPE chosenVPE;
if( (chosenVPE = XR_NakedNotifyInner(icv)) != NIL )
XR_RequestResched(chosenVPE);
}